//#define _CRT_SECURE_NO_WARNINGS 1
//
//class Solution {
//public:
//    Node* connect(Node* root) {
//        if (!root)return NULL;
//        queue<Node*>q;
//        q.push(root);
//
//        while (!q.empty()) {
//            int n = q.size();
//            Node* last = NULL;
//            for (int i = 0; i < n; i++) {
//                auto it = q.front();
//                q.pop();
//                if (it->left) {
//                    q.push(it->left);
//                }
//                if (it->right) {
//                    q.push(it->right);
//                }
//                if (i)last->next = it;
//                last = it;
//            }
//            last->next = NULL;
//        }
//        return root;
//    }
//};